1. Technical Field of the Invention
The present invention relates to computer-aided design (CAD) and, more particularly, to regularity extraction in the design of integrated circuits.
2. Background Art
In high-performance custom integrated circuit designs, designers take advantage of the high degree of regularity often present in circuits to generate efficient layouts in terms of area and performance as well as to reduce the design effort. Datapath circuits perform various arithmetic and multiplexing operations on wide buses. Such circuits have a very high degree of regularity. The design effort can be reduced by identifying or extracting regularity in circuits, thus improving the productivity of designers. Currently, however, datapath circuits in general-purpose microprocessors are designed almost entirely by hand. Existing CAD tools can not extract and utilize regularity to the extent necessary for competitive designs.
Various techniques for extraction of functional regularity have been proposed in the literature. For example, D. S. Rao et al., “On clustering for maximal regularity extraction,” IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 12, No. 8 (August 1993), pp. 1198-1208, describes a string matching algorithm to find all instances of user-specified templates in the circuit, and then heuristically choose a subset of the set of templates to cover the circuit. The final cover is sensitive to the templates provided by the designer. M. R. Corazao et al., “Performance optimization using template mapping for datapath-intensive high-level synthesis,” IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 15, No. 8 (August 1996), pp. 877-887, also assumes that a template library is provided, but claims to generate all complete as well as partial instances of a given template in the circuit. Another approach described in R. X. T. Nijssen et. al., “Regular layout generation of logically optimized datapaths,” Proc. Int'l Symp. on Physical Design, (1997), pp. 42-47, involves choosing small logic components, such as latches, as templates, and then growing them to obtain bigger templates. This approach is highly dependent on the initial choice of templates.
Various techniques for extraction of structural regularity have also been proposed in the literature. For example, G. Odawara et al., “Partitioning and Placement Technique for CMOS Gate Arrays,” IEEE Trans. on CAD, Vol. 6, No. 3 (May 1987), pp. 355-363, presents a methodology to identify structural regularity in highly-regular datapaths. Odawara's method chooses latches driven by the same control signals as initial templates, and uses them to grow larger templates. Odawara's approach identifies one-dimensional regularity in terms of bit-slices of the datapath. Other approaches by R. X. T. Nijssen et al, “Regular Layout Generation of Logically Optimized Datapaths,” Proc. Int's Symp. on Physical Design, (1997) pp. 42-47, and S. R. Arikati et al., “A Signature Based Approach to Regularity Extraction,” Proc. Int'l Conf. on CAD, (November 1997), pp. 542-545, extend Odawara's methodology to identify bit slices as well as stages of datapath circuits. However, these structural methods are not sufficient for circuits with a mix of datapath and control logic.
In the approaches in the above-listed articles opportunities for regularity extraction are missed. Furthermore, there is a need for a regularity extraction approach which would speed up technology mapping and layout generation of datapath circuits without comprising the final design quality.
Accordingly, there is a need for techniques for systematic regularity extraction.